package HashTable;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class _648_ReplaceWords {
    public String replaceWords_1(List<String> dict, String sentence) {
        Set<String> dicts = new HashSet<>();
        for (String d : dict) {
            dicts.add(d);
        }
        String[] words = sentence.split(" ");
        String ans = "";
        for (String word : words) {
            boolean contain = false;
            for (int i = 0; i < word.length(); i++) {
                String subs = word.substring(0, i + 1);
                if (dicts.contains(subs)) {
                    ans += subs;
                    contain = true;
                    break;
                }
            }
            if (!contain) {
                ans += word;
            }
            ans += " ";
        }
        return ans.substring(0, ans.length() - 1);
    }

    public String replaceWords(List<String> dict, String sentence) {
        TrieNode root = new TrieNode();
        for (String d : dict) {
            TrieNode cur = root;
            for (char c : d.toCharArray()) {
                if (cur.children[c - 'a'] == null) {
                    cur.children[c - 'a'] = new TrieNode();
                }
                cur = cur.children[c - 'a'];
            }
            cur.word = d;
        }

        StringBuffer sb = new StringBuffer();
        for (String sents : sentence.split(" ")) {
            TrieNode cur = root;
            for (char c : sents.toCharArray()) {
                if (cur.children[c - 'a'] == null || cur.word != null) {
                    break;
                }
                cur = cur.children[c - 'a'];
            }
            sb.append(cur.word != null ? cur.word : sents);
            sb.append(" ");
        }
        return sb.toString().substring(0, sb.length() - 1);
    }

    class TrieNode{
        TrieNode[] children;
        String word;
        public TrieNode() {
            children = new TrieNode[26];
        }
    }
}
